<?php
/**
 * 二分查找法优化 -- "插值查找"
 *  二分的含义是每次能够缩小到原有规模的 1/2; 这里的优化的是中间索引的位置, 因为有可能值并不是平均分布的, 如
 * [1, 2, 3, 4, 5, 6, 999,1000] 很显然 10 以内的数比较集中, 如果要查找 999, 那么应该尽量往后找, 转换为对应的公式就是
 * (1000 - 1) / (7-0) = 999 / 7 ≈ 142.4285714286; 说明如果平均分布的话, 每个值的间隔大概是 142.4285
 * (999 - 1)  / (mid - 0) = (1000 - 1) / (7-0) ≈ 142.4285714286;  mid = floor((998 * 7) / 999)  ≈ florr(6.99) = 6
 * 如果按照平均的算法的话 mid == 3, 所以平均算法需要查找的次数明显比插值查找要多
 * 优化的是中间索引的设置; 这里判断中间索引的偏移程度(偏左偏右)
 * User: yuesir
 * @author //github.com/yuesir
 */

/**
 *
 * @param array $bucket 要搜素的数组
 * @param mixed $target 要搜索的目标值
 * @return int 索引, 如果没有找到返回 -1
 */
function binarySearch(array $bucket, $target) {
    $index      = -1;
    $lowIndex   = 0;
    $minValue   = $bucket[$lowIndex];
    $highIndex  = count($bucket);
    $maxValue   = $bucket[$highIndex];

    while ($highIndex >= $lowIndex) {

        $midIndex   = floor($lowIndex + ($target - $minValue) * ($highIndex - $lowIndex) / ($maxValue - $minValue));
        $midValue   = $bucket[$midIndex];

        if ($midValue == $target) {
            $index = $midIndex;
        } elseif ($midValue > $target) {
            $lowIndex = $midIndex + 1;
        } else {
            $highIndex = $midIndex - 1;
        }

    }

    return $index;
}